package com.leetcode.lintcode;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/10/11 15:59
 */
public class MergekSortedArrays_486 {

    public int[] mergekSortedArrays(int[][] arrays) {
        int high = arrays.length, N = 0;
        Queue<int[]> queue = new PriorityQueue<>(high, Comparator.comparingInt(o -> o[0]));
        for (int i = 0; i < high; i++) {
            int len = arrays[i].length;
            if (len == 0) continue;
            int[] node = new int[3];
            node[0] = arrays[i][0];
            node[1] = i;
//            node[2] = 0;
            queue.offer(node);
            N += len;
        }

        int[] res = new int[N];
        int i = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            res[i++] = cur[0];
            // 结点到达当前数组的最后一位
            int arrayIndex = cur[1], index = cur[2];
            if (index == arrays[arrayIndex].length - 1) continue;
            cur[0] = arrays[arrayIndex][index + 1];
//            cur[1] = arrayIndex;
            cur[2] = index + 1;
            queue.offer(cur);
        }

        return res;
    }
}
